//https://leetcode.cn/problems/palindromic-substrings/submissions/564199985/

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();

        vector<vector<bool>> dp(n, vector<bool>(n));
        int ret = 0;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (s[i] == s[j])
                    dp[j][i] = j + 1 < i ? dp[j + 1][i - 1] : true;
                if (dp[j][i])
                    ret++;
            }
        }

        return ret;

    }
};